# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/23 18:49
@FileName      : 堆排序.py
@LastEditors   : None
@Editors       : PyCharm
"""
# 时间复杂度O(n+nlogn)
# 不稳定
'''二叉树'''


# 适合在很多元素中找很少几个top K的元素，或者在一个巨大的数据流里找到top K
def heapify(arr, n, i):
    largest = i  # 假设当前节点是最大值
    left = 2 * i + 1  # 左子节点
    right = 2 * i + 2  # 右子节点

    # 检查左子节点是否比当前节点大
    if left < n and arr[i] < arr[left]:
        largest = left

    # 检查右子节点是否比当前节点和左子节点都大
    if right < n and arr[largest] < arr[right]:
        largest = right

    # 如果根节点不是最大值，则交换根节点和最大值
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]

        # 对交换后的子树进行递归堆化
        heapify(arr, n, largest)


def heap_sort(arr):
    n = len(arr)

    # 构建最大堆，从最后一个非叶子节点开始堆化
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 从堆顶依次取出最大值，并重新堆化剩余元素
    for i in range(n - 1, 0, -1):
        print(arr)
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

    return arr


# 示例用法
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr)
print("result:", sorted_arr)
